package leetCode.offer04;


/**
 * 在一个 n * m 的二维数组中，每一行都按照从左到右非递减的顺序排序，
 * 每一列都按照从上到下非递减的顺序排序。
 * 请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 *
 * 示例:
 * 现有矩阵 matrix 如下：
 *
 * [
 *   [1,   4,  7, 11, 15],
 *   [2,   5,  8, 12, 19],
 *   [3,   6,  9, 16, 22],
 *   [10, 13, 14, 17, 24],
 *   [18, 21, 23, 26, 30]
 * ]
 *
 * 给定 target=5，返回true。
 * 给定 target=20，返回false。
 *
 * 限制：
 * 0 <= n <= 1000
 * 0 <= m <= 1000
 *
 */
public class Solution1 implements Solution {

    /**
     * 解题思路：
     * 这道题的思路关键在于找出数组中数的规律
     * 我们可以看到从右上角的数开始，左边的小于这个数，下边的大于这个数
     * @param matrix
     * @param target
     * @return
     */
    @Override
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix==null||matrix.length==0) return false;
        // 行长度
        int row = matrix.length;
        // 列长度
        int col = matrix[0].length;
        if(row==1&&col==1) {
            return matrix[0][0] == target;
        }
        // 定义初始坐标位置
        int rowPoint = row-1, colPoint = 0;
        for(int i=0;i<row*col;i++){
            if(matrix[rowPoint][colPoint] > target){
                if(rowPoint > 0){
                    rowPoint--;
                }
                else break;
            }
            else if(matrix[rowPoint][colPoint] < target){
                if(colPoint<col-1){
                    colPoint++;
                }
                else break;
            }
            else{
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {

//        System.out.println(new Solution1().findNumberIn2DArray());

    }


}
